package com.algrithom.bfs;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
import java.util.Stack;

/**
 * 301. 删除无效的括号
 * 
 * @author think
 */
public class Solution4 {
    
    public static void main(String[] args){
        Solution4 solution4 = new Solution4();
        System.out.println(solution4.removeInvalidParentheses("()())()"));
    }
    
    public List<String> removeInvalidParentheses(String s){
        Set<String> result = new HashSet<>();
        if (!s.contains("(") && !s.contains(")")) {
            result.add(s);
            return new ArrayList<>(result);
        }
        if (isRegularStr(s)) {
            result.add(s);
            return new ArrayList<>(result);
        }
        int len = s.length();
        
        for (int index = 0; index < len; index++) {
            String str = s.substring(0,index) + s.substring(index + 1);
            if (isRegularStr(str)) {
                result.add(str);
            }
        }
        if (result.size() == 0) {
            result.add("");
        }
        return new ArrayList<>(result);
    }
    
    private boolean isRegularStr(String str){
        Stack<Integer> stack = new Stack<>();
        int len = str.length();
        for (int index = 0; index < len; index++) {
            if (str.charAt(index) == '(' || str.charAt(index) == ')') {
                if (str.charAt(index) == '(') {
                    stack.push(index);
                } else if (stack.size() > 0 && str.charAt(index) == ')') {
                    stack.pop();
                } else {
                    return Boolean.FALSE;
                }
            }
        }
        return stack.size() > 0 ? Boolean.FALSE : Boolean.TRUE;
    }
}